SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Dynamic perfect hashing</title>

</head>

Dynamic perfect hashing

</h1>

</header>

In <a href="Computer_science" title="Computer science">computer science</a>, dynamic perfect hashing is a programming technique for resolving <a href="Hash_collision" title="Hash collision">collisions</a> in a <a href="Hash_table" title="Hash table">hash table</a> <a href="Data_structure" title="Data structure">data structure</a>.<a href="#cite_note-inventor-1">[1]</a><a href="#cite_note-dietzfelbinger-2">[2]</a><a href="#cite_note-3">[3]</a>

While more memory-intensive than its hash table counterparts, this technique is useful for situations where fast queries, insertions, and deletions must be made on a large set of elements.

<div class="mw-heading mw-heading2"><h2 id="Details">Details</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Static_case">Static case</h3></div>

<div class="mw-heading mw-heading4"><h4 id="FKS_Scheme">FKS Scheme</h4></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Static_hashing#FKS_Hashing" title="Static hashing">static hashing § FKS Hashing</a></div>

The problem of optimal <a href="Static_hashing" title="Static hashing">static hashing</a> was first solved in general by Fredman, Komlós and Szemerédi.<a href="#cite_note-4">[4]</a> In their 1984 paper,<a href="#cite_note-inventor-1">[1]</a> they detail a two-tiered hash table scheme in which each bucket of the (first-level) hash table corresponds to a separate second-level hash table. Keys are hashed twice—the first hash value maps to a certain bucket in the first-level hash table; the second hash value gives the position of that entry in that bucket's second-level hash table. The second-level table is guaranteed to be collision-free (i.e. <a href="Perfect_hashing" class="mw-redirect" title="Perfect hashing">perfect hashing</a>) upon construction. Consequently, the look-up cost is guaranteed to be <a href="Big_O_notation" title="Big O notation">O(1)</a> <a href="Worst-case_complexity" title="Worst-case complexity">in the worst-case</a>.<a href="#cite_note-dietzfelbinger-2">[2]</a>

In the static case, we are given a set with a total of x entries, each one with a unique key, ahead of time.

Fredman, Komlós and Szemerédi pick a first-level hash table with size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=2(x-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=2(x-1)}</annotation>

</semantics>

</math><img src="./00342f7424ef686e5b08d723b691ee57924c9ebc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.493ex; height:2.843ex;" alt="{\displaystyle s=2(x-1)}" loading="lazy"> buckets.<a href="#cite_note-dietzfelbinger-2">[2]</a>

To construct, x entries are separated into s buckets by the top-level hashing function, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=2(x-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=2(x-1)}</annotation>

</semantics>

</math><img src="./00342f7424ef686e5b08d723b691ee57924c9ebc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.493ex; height:2.843ex;" alt="{\displaystyle s=2(x-1)}" loading="lazy">. Then for each bucket with k entries, a second-level table is allocated with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k^{2}}</annotation>

</semantics>

</math><img src="./af6423cd00e3559de92c4bc497066ff1b12bbfc3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.265ex; height:2.676ex;" alt="{\displaystyle k^{2}}" loading="lazy"> slots, and its <a href="Hash_function" title="Hash function">hash function</a> is selected at random from a <a href="Universal_hash_function" class="mw-redirect" title="Universal hash function">universal hash function</a> set so that it is collision-free (i.e. a <a href="Perfect_hash_function" title="Perfect hash function">perfect hash function</a>) and stored alongside the hash table. If the hash function randomly selected creates a table with collisions, a new hash function is randomly selected until a collision-free table can be guaranteed. Finally, with the collision-free hash, the k entries are hashed into the second-level table.

The quadratic size of the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k^{2}}</annotation>

</semantics>

</math><img src="./af6423cd00e3559de92c4bc497066ff1b12bbfc3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.265ex; height:2.676ex;" alt="{\displaystyle k^{2}}" loading="lazy"> space ensures that randomly creating a table with collisions is infrequent and independent of the size of k, providing linear amortized construction time. Although each second-level table requires quadratic space, if the keys inserted into the first-level hash table are <a href="Uniform_distribution_(discrete)" class="mw-redirect" title="Uniform distribution (discrete)">uniformly distributed</a>, the structure as a whole occupies expected <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"> space, since bucket sizes are small with high <a href="Probability" title="Probability">probability</a>.<a href="#cite_note-inventor-1">[1]</a>

The first-level hash function is specifically chosen so that, for the specific set of x unique key values, the total space T used by all the second-level hash tables has expected <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"> space, and more specifically <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T<s+4\cdot x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T<s+4\cdot x}</annotation>

</semantics>

</math><img src="./77d4a841eb4f5c895bba0ec2863ef0d62e5ccabb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:12.837ex; height:2.343ex;" alt="{\displaystyle T<s+4\cdot x}" loading="lazy">.

Fredman, Komlós and Szemerédi showed that given a <a href="Universal_hashing" title="Universal hashing">universal hashing</a> family of hash functions, at least half of those functions have that property.<a href="#cite_note-dietzfelbinger-2">[2]</a>

<div class="mw-heading mw-heading3"><h3 id="Dynamic_case">Dynamic case</h3></div>

Dietzfelbinger et al. present a dynamic dictionary algorithm that, when a set of n items is incrementally added to the dictionary, membership queries always run in constant time and therefore <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"> worst-case time, the total storage required is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"> (linear), and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"> expected amortized insertion and deletion time (<a href="Amortized_constant_time" class="mw-redirect" title="Amortized constant time">amortized constant time</a>).

In the dynamic case, when a key is inserted into the hash table, if its entry in its respective subtable is occupied, then a collision is said to occur and the subtable is rebuilt based on its new total entry count and randomly selected hash function. Because the <a href="Hash_table#Load_factor" title="Hash table">load factor</a> of the second-level table is kept low <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/k}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1/k}</annotation>

</semantics>

</math><img src="./a7e9fedad8c70c6331b2640b56c23cef8c884e1f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.536ex; height:2.843ex;" alt="{\displaystyle 1/k}" loading="lazy">, rebuilding is infrequent, and the <a href="Amortized_analysis" title="Amortized analysis">amortized</a> expected cost of insertions is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy">.<a href="#cite_note-dietzfelbinger-2">[2]</a> Similarly, the amortized expected cost of deletions is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy">.<a href="#cite_note-dietzfelbinger-2">[2]</a>

Additionally, the ultimate sizes of the top-level table or any of the subtables is unknowable in the dynamic case. One method for maintaining expected <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation>

</semantics>

</math><img src="./34109fe397fdcff370079185bfdb65826cb5565a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" loading="lazy"> space of the table is to prompt a full reconstruction when a sufficient number of insertions and deletions have occurred. By results due to Dietzfelbinger et al.,<a href="#cite_note-dietzfelbinger-2">[2]</a> as long as the total number of insertions or deletions exceeds the number of elements at the time of last construction, the amortized expected cost of insertion and deletion remain <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"> with full rehashing taken into consideration.

The implementation of dynamic perfect hashing by Dietzfelbinger et al. uses these concepts, as well as <a href="Lazy_deletion" title="Lazy deletion">lazy deletion</a>, and is shown in pseudocode below.

<div class="mw-heading mw-heading2"><h2 id="Pseudocode_implementation">Pseudocode implementation</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Locate">Locate</h3></div>

<pre>function Locate(x) is

j := h(x)

if (position hj(x) of subtable Tj contains x (not deleted))

return (x is in S)

end if

else

return (x is not in S)

end else

end

</pre>

<div class="mw-heading mw-heading3"><h3 id="Insert">Insert</h3></div>

During the insertion of a new entry x at j, the global operations counter, count, is incremented.

If x exists at j, but is marked as deleted, then the mark is removed.

If x exists at j or at the subtable Tj, and is not marked as deleted, then a collision is said to occur and the jth bucket's second-level table Tj is rebuilt with a different randomly selected hash function hj.

<pre>function Insert(x) is

count = count + 1;

if (count > M)

FullRehash(x);

end if

else

j := h(x);

if (Position hj(x) of subtable Tj contains x)

if (x is marked deleted)

remove the delete marker;

end if

else

bj = bj + 1;

if (bj <= mj)

if position hj(x) of Tj is empty

store x in position hj(x) of Tj;

end if

else

Put all unmarked elements of Tj in list Lj;

Append x to list Lj;

bj = length of Lj;

repeat

hj = randomly chosen function in Hsj;

until hj is injective on the elements of Lj;

for all y on list Lj

store y in position hj(y) of Tj;

end for

end else

end if

else

mj = 2 * max{1, mj};

sj = 2 * mj * (mj - 1);

if the sum total of all sj ≤ 32 * M2 / s(M) + 4 * M

Allocate sj cells for Tj;

Put all unmarked elements of Tj in list Lj;

Append x to list Lj;

bj = length of Lj;

repeat

hj = randomly chosen function in Hsj;

until hj is injective on the elements of Lj;

for all y on list Lj

store y in position hj(y) of Tj;

end for

end if

else

FullRehash(x);

end else

end

</pre>

<div class="mw-heading mw-heading3"><h3 id="Delete">Delete</h3></div>

Deletion of x simply flags x as deleted without removal and increments count. In the case of both insertions and deletions, if count reaches a threshold M the entire table is rebuilt, where M is some constant multiple of the size of S at the start of a new phase. Here phase refers to the time between full rebuilds. Note that here the -1 in "Delete(x)" is a representation of an element which is not in the set of all possible elements U.

<pre>function Delete(x) is

count = count + 1;

j = h(x);

if position hj(x) of subtable Tj contains x

mark x as deleted;

end if

else

return (x is not a member of S);

end else

if (count >= M)

FullRehash(-1);

end if

end

</pre>

<div class="mw-heading mw-heading3"><h3 id="Full_rebuild">Full rebuild</h3></div>

A full rebuild of the table of S first starts by removing all elements marked as deleted and then setting the next threshold value M to some constant multiple of the size of S. A hash function, which partitions S into s(M) subsets, where the size of subset j is sj, is repeatedly randomly chosen until:

</mrow>

</munder>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{0\leq j\leq s(M)}s_{j}\leq {\frac {32M^{2}}{s(M)}}+4M.}</annotation>

</semantics>

</math><img src="./235d1cc5a19ca0dd4616718435917916e9b8431f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:27.126ex; height:7.343ex;" alt="{\displaystyle \sum _{0\leq j\leq s(M)}s_{j}\leq {\frac {32M^{2}}{s(M)}}+4M.}" loading="lazy">

Finally, for each subtable Tj a hash function hj is repeatedly randomly chosen from Hsj until hj is injective on the elements of Tj. The expected time for a full rebuild of the table of S with size n is O(n).<a href="#cite_note-dietzfelbinger-2">[2]</a>

<pre>function FullRehash(x) is

Put all unmarked elements of T in list L;

if (x is in U)

append x to L;

end if

count = length of list L;

M = (1 + c) * max{count, 4};

repeat

h = randomly chosen function in Hs(M);

for all j < s(M)

form a list Lj for h(x) = j;

bj = length of Lj;

mj = 2 * bj;

sj = 2 * mj * (mj - 1);

end for

until the sum total of all sj ≤ 32 * M2 / s(M) + 4 * M

for all j < s(M)

Allocate space sj for subtable Tj;

repeat

hj = randomly chosen function in Hsj;

until hj is injective on the elements of list Lj;

end for

for all x on list Lj

store x in position hj(x) of Tj;

end for

end

</pre>

<ul><li><a href="Perfect_hashing" class="mw-redirect" title="Perfect hashing">Perfect hashing</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-inventor-1">^ <a href="#cite_ref-inventor_1-0">a</a> <a href="#cite_ref-inventor_1-1">b</a> <a href="#cite_ref-inventor_1-2">c</a> Fredman, M. L., Komlós, J., and Szemerédi, E. 1984. Storing a Sparse Table with 0(1) Worst Case Access Time. J. ACM 31, 3 (Jun. 1984), 538-544 <a rel="nofollow" class="external free" href="http://portal.acm.org/citation.cfm?id=1884#">http://portal.acm.org/citation.cfm?id=1884#</a>

</li>

<li id="cite_note-dietzfelbinger-2">^ <a href="#cite_ref-dietzfelbinger_2-0">a</a> <a href="#cite_ref-dietzfelbinger_2-1">b</a> <a href="#cite_ref-dietzfelbinger_2-2">c</a> <a href="#cite_ref-dietzfelbinger_2-3">d</a> <a href="#cite_ref-dietzfelbinger_2-4">e</a> <a href="#cite_ref-dietzfelbinger_2-5">f</a> <a href="#cite_ref-dietzfelbinger_2-6">g</a> <a href="#cite_ref-dietzfelbinger_2-7">h</a> Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, R. E. 1994.

<a rel="nofollow" class="external text" href="http://www.arl.wustl.edu/~sailesh/download_files/Limited_Edition/hash/Dynamic%20Perfect%20Hashing-%20Upper%20and%20Lower%20Bounds.pdf">"Dynamic Perfect Hashing: Upper and Lower Bounds"</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160304094014/http://www.arl.wustl.edu/~sailesh/download_files/Limited_Edition/hash/Dynamic%20Perfect%20Hashing-%20Upper%20and%20Lower%20Bounds.pdf">Archived</a> 2016-03-04 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a>.

SIAM J. Comput. 23, 4 (Aug. 1994), 738-761.

<a rel="nofollow" class="external free" href="http://portal.acm.org/citation.cfm?id=182370">http://portal.acm.org/citation.cfm?id=182370</a>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0097539791194094">10.1137/S0097539791194094</a>

</li>

Erik Demaine, Jeff Lind.

<a rel="nofollow" class="external text" href="http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L2/lecture2.pdf">6.897: Advanced Data Structures</a>.

MIT Computer Science and Artificial Intelligence Laboratory. Spring 2003.

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFYap" class="citation web cs1">Yap, Chee. <a rel="nofollow" class="external text" href="ftp://cs.nyu.edu/pub/local/yap/cg/hashFKS.ps.gz">"Universal Construction for the FKS Scheme"</a>. New York University (<a href="FTP" class="mw-redirect" title="FTP">FTP</a>). Retrieved 15 February 2015.</cite> (To view documents see Help:FTP)

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-27" href="https://en.wikipedia.org/wiki/?title=Dynamic_perfect_hashing&oldid=1292513176">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>